package leetcode.editor.offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 剑指 Offer 39. 数组中出现次数超过一半的数字
// https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
class ShuZuZhongChuXianCiShuChaoGuoYiBanDeShuZiLcof {
    public static void main(String[] args) {
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class SolutIion {
        // 哈希表
        /*public int majorityElement(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }

            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() > nums.length / 2) return entry.getKey();
            }

            return 0;
        }*/

        // 排序后取中间值(排序法)
        /*public int majorityElement(int[] nums) {
            Arrays.sort(nums);
            return nums[nums.length / 2];
        }*/

        // 投票法
        public int majorityElement(int[] nums) {
            int x = 0, votes = 0;
            for (int num : nums) {
                if (votes == 0) x = num;
                if (num == x) votes++;
                else votes--;
            }

            // 如果不存在众数，需要遍历x进行验证本题说明了存在众数
            /*int count = 0;
            for (int num : nums) {
                if (x == num) count++;
            }
            if (count > nums.length / 2) return x;*/

            return x;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
